1. The Field of the Invention
The present invention generally relates to synchronizing data within a distributed computer system. More particularly, the present invention provides for consistent resolution of data conflicts when synchronizing data between two or more devices in order to reduce the likelihood of an infinite synchronization loop.
2. Background and Related Art
Laptop, handheld, and other portable computers or computing devices have increased in popularity as the devices become smaller in size and less expensive. Additionally, improved operating speed and processing power of portable computers has increased their popularity. Many portable computers are capable of storing multiple application programs, such as address books, games, calculators, and the like. The application programs can be permanently installed in the portable computer during manufacture (e.g., on Read-Only Memory (ROM)). Alternatively, one or more application programs may be installed by the user after purchasing the portable computer.
With the increased popularity and computing power of such devices, people are beginning to store data and applications using more than just a single computing device. Many people, for example, often use laptop computers in addition to their regular desktop computer. Other devices such as cellular telephones, Personal Digital Assistance (PDAs), Internet services, and the like are also used for storing data and applications.
Each of these computing devices may be part of a distributed computing system wherein related information can be correlated and stored on multiple such devices. For example, a user may have a digital address book stored on their desktop work computer, on their PDA, on their cell phone, on an Internet service, etc. Accordingly, while at work, it may be convenient for the user to access contact information, which may include phone numbers and other general contact information. While away from work, however, the user may be able to use the address book in a mobile form such as a personal digital assistance (PDA) or other mobile information storage system. Ideally, the contact information of the PDA should match the contact information at the desktop work computer.
When the same or related information is stored in two places, it is possible for the data to change in one location and not in the other. This problem may be overcome through synchronization, which is an automated process that attempts to ensure that each device within the distributed system has the most current information or data. Synchronization, however, has its own set of problems. For example, when synchronization is initialized between the two devices, current systems detect changed property values by comparing corresponding property values from each device. Such comparison, however, gives no indication as to which device made the change. As such, when a property change has occurred on either device, a conflict occurs and a conflict resolution process must be performed.
Other systems mark a changed property with a tag indicating that a change has occurred, e.g., “change,” “delete,” “add,” or other tag, as appropriate. In such systems, however, when two devices start syncing, one of the devices can create these markers in memory after comparing the data for what needs to be applied. In other words, conflicts must first be reconciled and then the properties can be marked.
Typically, conflicts can be resolved through comparing metadata associated with the property values that give, e.g., time date information. The latest time date information may be considered the most up-to-date information and the properties can be updated accordingly. Many smaller computing devices, however, have limited physical resources and are incapable of maintaining time date information for properties of a data structure item. Further, in a distributing computing network there is typically no single server with a “master” copy of data that can be used to resolve discrepancies or conflicts. Accordingly, in such situations, typically a User Interface (UI) is presented to a user notifying them of the conflict and directing them to choose what value to use to resolve the conflict. This process can become, however, tedious in the event of numerous conflicts and can degrade the user experience.
Some systems have attempted to overcome the above problem by presenting a default value to the user or to resolve the conflict automatically. In either event, the choice is typically based on arbitrary techniques and considerations such as network topology. For example, some systems choose a default value or resolve the conflict through rules that choose the values based on a particular nodes status (e.g., location) within the network. For instance, one rule for resolving conflicts may mandate that if a conflict exits, all servers values should win, or if the choose is between a high fidelity and low fidelity device, then all high fidelity device values should be chosen. Of course, there are a number of network topology choices or other similar choices available.
Although selecting a value based on network topology resolves the conflict, this can also result in values being essentially continuously transferred between nodes in the distributed computing system, which is termed an infinite loop. In such situations, the user can be continually presented with choices of opposing default values to resolve the conflict and/or the data is continually updated on the devices and the user will have to provide some type of intervention in order to stop the changing of the data. Further, continuously transferring data between nodes in a distributed system unnecessarily consumes network bandwidth, preventing other modules from utilizing the network bandwidth. As such, it is desirable to be able to break infinite loops in a distributed network system in order to ensure a good user experience and preserve valuable processing resources.